N = 2000;
T = [1742,1567,226,42,1624,1876,1267,863,1396,313,1278,814,886,1246,84,1573,1191,1458,667,1720,372,1125,102,1636,1656,230,1554,1205,884,1866,1801,410,183,1463,983,1684,1437,639,1006,48,1589,736,500,1449,1949,1617,714,1032,526,22,753,780,416,519,143,1607,1709,1959,1352,632,1196,940,437,1452,1918,1865,804,201,918,1769,950,599,547,155,1931,1621,1031,848,506,626,311,1966,38,1366,865,55,951,1713,1930,95,775,1257,933,849,1390,1085,330,848,669,1643,382,645,314,1129,1175,1446,1767,1994,1861,984,434,1333,1503,1380,1491,263,295,1780,1303,448,491,1560,815,1643,278,653,1576,1891,818,596,1464,1237,1616,1188,1623,1134,1541,1556,976,87,1263,905,1078,439,132,1765,1468,1335,796,836,290,82,1093,363,1448,1705,666,1590,1841,746,679,676,1387,154,1058,1401,543,383,1582,1591,1106,1280,1948,854,482,1981,323,1871,1682,1945,741,1942,302,1908,1497,395,103,805,63,254,150,4,28,1481,744,1972,1867,1761,769,1814,35,86,799,1337,449,94,1174,1708,1140,299,70,1633,708,323,166,1654,1912,1920,217,169,1298,66,1737,1281,1079,374,214,882,1299,1371,1475,1789,981,1864,1309,1024,1105,776,221,892,223,153,1693,108,1466,131,1665,1394,1865,1518,1650,923,595,1753,448,117,50,71,17,221,561,1979,1057,592,1242,1914,671,1461,1823,90,1100,148,1710,1700,213,821,1682,314,281,728,233,605,648,1015,304,495,408,802,13,1087,1257,863,235,1761,1867,1912,269,1984,56,1664,1155,966,1262,938,683,699,1794,1023,195,1366,67,135,248,1325,121,349,755,612,536,1038,838,1646,613,1968,86,1264,683,215,1238,418,1589,584,1522,702,182,1898,810,163,1465,265,988,289,1643,287,265,126,190,46,672,1274,1942,1170,1001,179,1437,15,1392,1815,918,145,1331,1406,965,1245,272,334,1062,1197,1794,1912,909,622,417,1739,788,1148,1259,710,382,1040,361,51,1034,1341,594,979,64,1338,462,1209,1889,1443,1186,1123,85,590,1184,71,730,452,16,1160,1628,1633,1852,761,148,189,64,1259,711,375,1900,1777,985,513,1026,1583,442,1192,1914,1586,81,510,1581,402,1105,39,730,1352,1137,1104,1703,1958,686,1976,1864,1439,641,831,16,175,781,801,778,392,1821,1081,1972,1395,1662,1993,1414,77,1680,912,628,1629,1185,1434,832,1330,161,977,1663,884,1259,1353,1848,1524,1364,1580,1288,651,704,430,1995,1524,1867,996,1947,1692,624,230,436,693,1552,86,772,1482,1045,185,1518,1665,1008,115,727,1709,202,1883,736,1657,406,818,374,883,424,124,1547,1529,430,1889,677,1925,631,275,852,67,524,1162,307,283,984,817,407,1836,123,1704,1368,32,544,1141,290,800,1033,225,1078,1633,164,642,294,183,915,1190,1765,816,1227,83,374,1483,1044,257,1208,237,785,1398,813,1100,594,1662,1759,1389,1572,1175,602,1440,179,984,1413,761,299,1797,1803,151,1224,18,1657,567,807,247,772,72,1830,610,428,1502,1269,805,1801,276,1985,1072,1826,1435,165,1086,521,487,1924,1679,1303,245,1999,1504,1147,879,798,553,1352,1647,444,719,30,130,1438,1180,1180,1119,930,1815,1290,508,255,1571,882,860,289,726,231,1144,1492,1558,1397,1209,712,1563,712,562,1854,628,231,1112,162,790,1919,1188,387,1875,103,672,555,152,1411,305,100,1148,539,672,814,206,1819,1644,540,1322,61,750,1890,660,1297,611,118,1980,665,1313,619,1418,1264,1896,1051,438,1192,1312,432,1776,259,621,572,1345,1838,1940,268,1731,1457,974,1422,536,1169,1060,1097,1803,1032,1314,44,530,869,8,1092,1910,1510,587,1977,41,636,1623,1486,618,1064,1593,352,1946,1622,1739,94,1057,600,304,1206,1762,847,665,1368,627,939,210,254,618,1949,156,1100,398,1356,1815,677,3,162,1243,268,127,603,1974,1937,798,286,1812,94,356,1386,1011,287,736,872,763,1443,1548,291,3,1377,111,1521,942,1051,161,21,1119,937,138,618,758,188,839,1141,1055,1902,1060,904,658,437,907,1646,855,220,211,432,638,264,675,805,1065,23,1776,1478,1359,131,1586,862,699,133,351,442,1285,853,745,1126,1423,1955,1729,747,1859,1388,1087,903,788,1950,1703,1288,1867,178,1921,1854,1261,1604,1020,1070,288,1627,695,1699,1917,1944,851,929,1567,269,304,824,1872,1970,1082,49,946,1242,459,1631,656,1091,718,352,29,444,1370,1948,1799,814,1553,366,252,854,1815,646,1618,667,1386,249,408,1278,9,853,15,615,333,40,1223,978,236,408,1381,201,1451,678,125,140,1068,431,896,691,1345,458,278,606,186,296,540,1752,1282,81,78,456,371,1388,617,622,1405,406,400,1769,337,595,1117,1746,52,329,1199,243,474,1535,583,73,765,1010,595,1464,996,1167,1030,1919,200,438,754,674,341,828,759,423,488,232,457,1028,794,554,970,566,22,436,1632,1105,1064,661,484,532,166,26,1772,324,1128,1865,395,461,888,1354,778,348,1818,1189,1931,266,235,1241,4,1474,1749,687,1194,1302,1733,1338,1684,527,545,483,921,534,301,1368,574,391,902,1223,316,1830,1560,214,833,164,93,389,506,979,136,1007,1578,173,624,317,1135,1534,497,239,19,581,947,1056,1313,1796,274,1902,838,367,1590,1128,1029,318,625,258,319,1580,496,820,1855,992,485,14,1916,546,561,880,1057,10,342,997,419,1320,919,419,126,1699,1447,1089,97,1947,1779,1019,105,256,1629,53,612,1576,586,1469,203,1290,1559,160,689,379,788,1565,442,1747,640,741,1954,47,573,444,770,633,1181,1375,262,709,678,21,438,411,74,1941,1793,613,589,1396,1434,204,1900,638,1973,563,1752,1505,401,752,1109,1241,744,697,971,144,864,980,253,1082,1835,1627,42,520,1686,1795,1102,543,1885,1531,24,1805,1541,1515,657,1033,814,1277,570,563,664,256,1194,705,287,1150,1554,809,39,1420,574,1014,1376,473,508,1525,260,875,690,1375,1480,221,1720,373,762,733,1889,1645,453,613,1152,842,9,1778,9,1105,2000,902,767,380,702,764,973,546,82,1973,156,1715,827,1595,123,1631,634,1906,484,491,582,1547,543,976,513,729,1954,739,791,1195,172,273,1039,1198,443,851,529,78,958,1640,259,1637,1133,531,222,351,547,411,719,879,1651,454,2,1542,1890,52,1835,154,550,576,1273,1230,1956,1391,174,831,336,1953,1766,1439,1061,1965,501,681,528,210,1963,44,562,1918,603,1199,324,1615,20,1831,1470,568,1105,1249,405,2000,1826,706,1813,1005,1724,242,1005,1090,1680,1974,1943,409,431,1767,70,1725,244,1258,1619,1286,1587,24,1171,1126,790,435,174,661,1211,764,303,918,694,373,515,659,1847,886,1016,1987,24,733,1833,307,1421,199,1287,1623,1054,364,60,1938,1085,1111,1950,715,1702,1137,481,1465,1385,241,502,1413,258,1239,131,616,34,1984,1429,550,62,1987,1333,149,396,893,187,1020,104,1228,1991,856,98,196,573,226,223,487,209,1735,1770,627,1315,1438,977,317,1860,1053,1750,347,794,1176,824,1197,298,1310,1398,198,1220,1207,1620,237,1399,1186,480,1605,1042,338,1771,122,1384,1181,669,776,128,992,1835,605,14,1159,1379,1938,1196,1562,869,1014,1565,962,279,1393,36,1569,1670,1666,1202,1128,941,710,945,251,1471,1821,1422,361,1162,1660,1751,571,1054,320,1478,869,748,397,1420,507,713,516,1957,1014,1257,466,955,492,91,1640,1271,159,37,1244,890,1130,813,1819,1515,1096,1255,148,1563,263,324,745,1017,207,1550,1482,600,784,772,1453,493,1149,1431,1015,1403,976,601,486,399,782,494,1707,1312,1298,1621,405,447,19,1341,205,1212,1335,2,1026,65,1770,1999,350,1053,129,515,434,847,756,1241,1943,733,608,1392,630,1486,795,1877,1111,734,1472,1876,327,791,852,360,1162,1939,998,1432,85,498,359,1762,1151,439,1735,1063,1379,968,381,255,1112,216,1795,1701,1867,1476,1656,14,191,843,1372,1048,802,244,707,1410,631,1967,331,1936,1509,1429,1306,1981,475,569,1344,133,1742,446,1777,179,350,1561,1213,1058,213,1419,7,896,242,337,519,264,908,918,1219,170,194,399,1538,1245,1877,238,1139,107,1738,1323,1226,279,1299,1053,717,1186,1040,1469,1622,780,1672,1884,308,1888,822,563,359,1467,1168,1660,533,685,62,353,720,1949,1321,208,1136,1157,1002,1332,1792,305,1806,1828,1822,1812,1596,1611,818,593,531,317,1023,111,1231,280,1095,58,1153,1345,1475,1926,1409,664,436,384,1131,1968,1601,611,647,308,1453,1632,591,415,332,1219,1007,599,215,1872,1733,971,1121,1871,1623,1225,1941,220,339,1902,1434,1662,1519,1696,1015,104,1103,1569,1346,578,975,141,1412,79,797,1027,356,838,1252,202,1364,870,1326,1760,936,1549,565,559,1123,1842,1921,214,142,107,1857,1661,11,1281,484,1052,1687,274,1254,1992,80,515,327,323,1467,1597,1868,751,1376,469,924,1252,1646,472,1036,1514,117,157,1447,1002,1192,405,1721,477,1633,48,1897,630,1484,1110,1115,751,551,284,891,1912,362,578,1423,7,37,1030,1472,1628,1913,1287,1773,1361,1083,1036,1627,425,492,671,762,420,929,673,431,512,272,49,128,236,1295,1770,468,109,1118,1459,1382,1308,1930,614,1300,1974,823,1608,1221,689,1945,1545,1372,1798,375,640,590,1479,779,1240,1351,1468,1255,1915,887,891,1346,972,1908,475,754,1354,643,1933,1694,1425,548,690,807,459,1503,1540,1046,1802,1279,1659,1606,183,276,1581,1673,631,1754,800,396,1172,1535,1430,787,1229,1610,1968,554,1507,465,1077,193,635,1834,662,1768,1157,1531,426,1791,125,514,209,913,44,929,1652,999,1844,1965,1865,71,1269,1691,257,240,1394,1441,1468,1477,1975,1869,857,709,154,1520,1535,946,1267,1713,593,1092,990,1818,75,1402,1073,31,270,1301,1454,400,171,866,481,556,1551,1374,811,620,1536,1041,1508,1265,967,667,522,618,1217,939,229,382,1811,5,146,326,1136,1804,604,400,1630,1748,168,1428,43,306,1098,450,1594,1415,1044,1141,678,933,697,1261,106,1021,989,470,1367,1057,1583,575,1378,498,291,637,1265,1898,1380,1061,993,1723,153,1464,1352,1756,1408,614,692,469,348,1622,309,1272,617,313,1915,422,738,1664,218,1718,644,979,124,1933,867,88,960];